#include "circ.h"

int circ_insert(struct node_st **p, int value)
{
	struct node_st * newnode = malloc(sizeof(struct node_st));
	if(newnode == NULL)
		return -1;
	newnode->value = value;
	struct node_st * current = *p;
	if(current == NULL)
	{
		newnode->next = newnode;
		*p = newnode;
		return 0;
	}
	while(current->next != *p)
		current = current->next;
	newnode->next = *p;
	current->next = newnode;
	return 0;
}

//(老师写法)
//int circ_insert(struct node_st **p, int value)
//{
//	struct node_st *newnode = malloc(sizeof(*newnode));
//	if (newnode == NULL)
//		return 0;
//	struct node_st *current = *p;
//	if (current == NULL)    
//	{
//		*p = newnode;
//		newnode->value = value;
//		newnode->next = newnode;
//		return 1;
//	}
//
//	while (current && current->next != *p)
//		current = current->next;
//	current->next = newnode;
//	newnode->next = *p;
//	newnode->value = value;
//	return 1;
//}

//删除第num个结点
int circ_remove(struct node_st **p, int num)
{
	if(num <= 0)
		return -1;
	struct node_st *current = *p;
	if(current == NULL)
		return -2;
	int i = 1;
	struct node_st *pre = current;
	if(num == 1)            //删除第一个元素需要修改头指针指向
	{
		while (pre->next != current)
			pre = pre->next;
		pre->next = current->next;
		*p = current->next;
		free(current);
		return 0;
	}
	while(i != num && current->next != *p)  
	{
		pre = current;
		current = current->next;
		i++;
	}
	if (i != num && current->next == *p)       //num大于链表所含元素个数
		return -1;
	else
	{
		pre->next = current->next;
		free(current);
		return 0;
	}
	return -3;       //不存在
}

void circ_show(struct node_st *p)
{
	struct node_st *current = p;
	while (current && current->next != p)
	{
		printf("%d  ", current->value);
		current = current->next;
	}
	printf("%d  ", current->value);
}

void Josephus(struct node_st **p, int m, int n)
{
	for (int i = 0; i < m; i++)
		circ_insert(p, i + 1);
	circ_show(*p);
	printf("\n");
	int val = 1;
	while ((*p)->next != *p)
	{
		circ_remove(p, val);
		val += n;
	}
	printf("赢得机会的人是%d\n", (*p)->value);
}